Nguyễn Bá Tòng sinh ngày 7 tháng 8 năm 1868 tại tỉnh Gò Công (nay thuộc thị xã Gò Công, tỉnh Tiền Giang) trong một gia đình đạo đức.[6] Cha mẹ ông là ông Giacôbê Nguyễn Gia Tuấn và bà Mađalêna Nguyễn Thị Chi.[7] Thân phụ ông trước có du học Penang, sau này trở về Việt Nam hành nghề thông dịch viên tại Gò Công và Trà Vinh.[6]

Năm 1878, khi lên 10 tuổi, cậu bé Nguyễn Bá Tòng được gửi vào trường Tiểu học La San tại Định Tường. Khi ngôi trường bị đóng cửa năm 1880, cậu được gửi về Sài Gòn và theo học Collège d’Adran. Tại đây, cậu được gặp linh mục Jean Dépierre (tên Việt: Để, 1855 - 1898), giáo sư môn Latinh Tiểu chủng viện Sài Gòn kiêm Tuyên úy trường La san d’Adran, quý mến và đỡ đầu. Lên 15 tuổi, linh mục Dépierre Để giới thiệu cậu bé Tòng vào học Tiểu chủng viện, thời gian này dưới quyền giám đốc của Linh mục Thiriet, là một người thông thái. Những năm học ở Tiểu chủng viện, cậu luôn được xem là một chủng sinh xuất sắc.[7] Năm 1887, chủng sinh Nguyễn Bá Tòng được nhận vào học Đại chủng viện Sài Gòn và học tại đây cho đến khi tốt nghiệp năm 1896.[8]